package com.xhj.joffer.tree;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
/** @author haijianxia pure_xhj@163.com @Date 2021-09-06 @Time 17:24 */
public class PrintTree {
  public static void main(String[] args) {
    /** root t1 | t2 t3 | t4 t5 | t6|t7 |t8 t9| */
    TreeNode root = new TreeNode("root");
    TreeNode t1 = new TreeNode("t1");
    TreeNode t2 = new TreeNode("t2");
    TreeNode t3 = new TreeNode("t3");
    TreeNode t4 = new TreeNode("t4");
    TreeNode t5 = new TreeNode("t5");
    TreeNode t6 = new TreeNode("t6");
    TreeNode t7 = new TreeNode("t7");
    TreeNode t8 = new TreeNode("t8");
    TreeNode t9 = new TreeNode("t9");
    root.setleftAndright(t1, t2);
    t1.setleftAndright(t3, t4);
    t2.setleftAndright(t5, null);
    t3.setleftAndright(t6, t7);
    t5.setleftAndright(null, t8);
    t6.setleftAndright(t9, null);

    String s = TreeNodes.testPrint("str: ", root); // - - - - - - -深度-左序 递归打印
    System.out.println("\ns = " + s);
    System.out.println("====================================================");

    String s02 = TreeNodes.testDeepRightPrint("02: ", root);
    System.out.println("s02 = " + s02);
    System.out.println("====================================================");
  }
}

class TreeNodes {
  // 深度优先-广度优先
  // 先序-中序-后序

  /** 深度-先序 思路一:递归法 */
  @Test
  public int[] test01(TreeNode root) {
    System.out.println("=============test01==============");
    System.out.println("深度-先序");
    long time01 = System.currentTimeMillis();

    // int[] result=new int[?];
    List<Integer> resultList = new ArrayList<Integer>();

    long time0101 = System.currentTimeMillis() - time01;
    System.out.println("\ntest01 耗时 =  " + time0101 + "ms");
    System.out.println("=================================");

    int[] result = new int[resultList.size()];
    for (int i = 0; i < result.length; i++) {
      result[i] = resultList.get(i);
    }
    return result;
  }
  /**
   * 判断一个整数数组是不是某二叉搜索树的后续遍历结果
   *
   * @return
   */
  @Test
  public boolean testVerifyPostorder(int[] postorder) {
    System.out.println("=============testVerifyPostorder==============");
    System.out.println("判断一个整数数组是不是某二叉搜索树的后续遍历结果");
    long timeVerifyPostorder = System.currentTimeMillis();

    boolean result = false;

    long timeVerifyPostorderVerifyPostorder = System.currentTimeMillis() - timeVerifyPostorder;
    System.out.println("\ntestVerifyPostorder 耗时 =  " + timeVerifyPostorderVerifyPostorder + "ms");
    System.out.println("=================================");

    return result;
  }
  /** 递归打印 */
  @Test
  public static String testPrint(String str, TreeNode root) {
    str += root.getValue() + ", "; // - - - - - - -添加当前节点value值, 并送入下次递归操作
    System.out.print(root.getValue() + ", "); // - - - - - - -打印当前节点值
    if (root.getLeft() != null) {
      str = testPrint(str, root.getLeft()); // - - - - - - -如果有左节点, 则刷新str值
    }
    if (root.getRight() != null) {
      str = testPrint(str, root.getRight());
    }
    return str;
  }
  /** 深度-后续 递归打印 */
  @Test
  public static String testDeepRightPrint(String str, TreeNode root) {
    str += root.getValue() + ", ";
    if (root.getRight() != null) {
      str = testDeepRightPrint(str, root.getRight());
    }
    if (root.getLeft() != null) {
      str = testDeepRightPrint(str, root.getLeft());
    }
    return str;
  }

  /** 深度-先序 递归转循环 */
  @Test
  public static String testRecursionToWhile(String str, TreeNode root) {
    System.out.println("=============testRecursionToWhile==============");
    System.out.println("深度-先序  递归转循环");
    long timeRecursionToWhile = System.currentTimeMillis();

    String result = "";

    long timeRecursionToWhileRecursionToWhile = System.currentTimeMillis() - timeRecursionToWhile;
    System.out.println(
        "\ntestRecursionToWhile 耗时 =  " + timeRecursionToWhileRecursionToWhile + "ms");
    System.out.println("=================================");

    return result;
  }
}

class TreeNode {
  private String value;
  private TreeNode left;
  private TreeNode right;

  public TreeNode() {}

  public TreeNode(String value) {
    this.value = value;
  }

  public TreeNode(String value, TreeNode left, TreeNode right) {
    this.value = value;
    this.left = left;
    this.right = right;
  }

  public String getValue() {
    return value;
  }

  public TreeNode getLeft() {
    return left;
  }

  public TreeNode getRight() {
    return right;
  }

  public TreeNode setValue(String value) {
    this.value = value;
    return this;
  }

  public TreeNode setLeft(TreeNode left) {
    this.left = left;
    return this;
  }

  public TreeNode setRight(TreeNode right) {
    this.right = right;
    return this;
  }

  public TreeNode setleftAndright(TreeNode left, TreeNode right) {
    this.left = left;
    this.right = right;
    return this;
  }
}
